{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "14800f61",
   "metadata": {},
   "source": [
    "[121. 买卖股票的最佳时机 - 力扣（LeetCode）](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "af9f5e48",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "## 最大收益\n",
    "## 直接模拟超时，\n",
    "# 使用动态规划\n",
    "# 定义dp[i] 为第i天购入时能获得的最大收益\n",
    "# dp[n-1] = -price[n-1]  \n",
    "## dp[i]>0 表示prices[i] 右边的值有比其大的\n",
    "## dp[i]<0 表示prices[i] 右边的值都比其小\n",
    "# dp[i-1] = price[i]-price[i-1]  if dp[i]<0\n",
    "#         = price[i]-price[i-1] + dp[i] if dp[i]>0\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = n*[0]\n",
    "        dp[n-1] = -prices[n-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if dp[i+1]>0:\n",
    "                dp[i] = prices[i+1]-prices[i] + dp[i+1]\n",
    "            else:\n",
    "                dp[i] = prices[i+1]-prices[i]\n",
    "        \n",
    "        return max(0,max(dp))\n",
    "\n",
    "\n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.maxProfit([7,1,5,3,6,4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2e10a28d",
   "metadata": {},
   "source": [
    "[122. 买卖股票的最佳时机 II - 力扣（LeetCode）](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "649817e2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n"
     ]
    }
   ],
   "source": [
    "## 贪心算法\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "# 最大股票收益问题\n",
    "# 注意1）当天买入后可以卖出\n",
    "#     2）当天卖出后还可以买入\n",
    "# 使用贪心算法计算\n",
    "# 1）如果明天价格比今天高就今天买入明天卖出获取收益，否则今天就卖出止损也即收益为0\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        res = 0\n",
    "        for i in range(n-1):\n",
    "            if prices[i]<prices[i+1]: # 明天价格高，明天卖\n",
    "                res += prices[i+1]-prices[i]\n",
    "            # 否则今天就卖，收益为0\n",
    "        return res\n",
    "\n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.maxProfit([7,1,5,3,6,4]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f05f85c5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n"
     ]
    }
   ],
   "source": [
    "## 动态规划的解法\n",
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 使用动态规划求解股票最大收益问题\n",
    "# 每天交易完成后对应两种状态：手里有股票，手里没有股票\n",
    "# 定义dp[i][0]: 截至到第i天手里没有股票时，能获得的最大收益\n",
    "# 定义dp[i][1]: 截至到第i天手里有股票时，能获得的最大收益\n",
    "# 初始化\n",
    "# dp[0][0] = 0,dp[0][1]=-prices[0]\n",
    "# 转移方程\n",
    "# dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])\n",
    "# dp[i][1] = max(dp[i-1][0]-prices[i],dp[i-1][1])\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[0]*2 for _ in range(n)]\n",
    "\n",
    "        dp[0][0], dp[0][1] = 0, -prices[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])\n",
    "            dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])\n",
    "        return dp[n-1][0]\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.maxProfit([7, 1, 5, 3, 6, 4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "006b2e9e",
   "metadata": {},
   "source": [
    "[123. 买卖股票的最佳时机 III - 力扣（LeetCode）](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d735963b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 使用动态规划\n",
    "# 分析，每天的交易结束后，一共存在5种状态\n",
    "# 1. 没有交易行为\n",
    "# 2. 买入股票\n",
    "# 3. 完成一次交易\n",
    "# 4. 完成一次交易的前提下，买入股票\n",
    "# 5. 完成两次交易\n",
    "# 更新每一天的这五个状态就，最后一天的状态3，和5的最大值就是所求，第一种状态不会对收益有影响可以忽略\n",
    "# 定义状态dp[i][0],dp[i][1],...,dp[i][3] 表示截至到第i天交易后状态2-4对应的最大收益\n",
    "# 状态转移方程\n",
    "# dp[i][0] = max(dp[i-1][0],-prices[i])\n",
    "# dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])\n",
    "# dp[i][2] = max(dp[i-1][2],dp[i-1][1]-prices[i])\n",
    "# dp[i][3] = max(dp[i-1][3],dp[i-1][3]+prices[i])\n",
    "# 初始化\n",
    "# dp[0][0] = -prices[0]\n",
    "# dp[0][1] = 0\n",
    "# dp[0][2] = -prices[0]\n",
    "# dp[0][3] = 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, prices: List[int]) -> int:\n",
    "        n = len(prices)\n",
    "        dp = [[0]*4 for _ in range(n)]\n",
    "        # initialize\n",
    "        dp[0][0], dp[0][1] = -prices[0], 0\n",
    "        dp[0][2], dp[0][3] = -prices[0], 0\n",
    "        # update\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = max(dp[i-1][0], -prices[i])\n",
    "            dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])\n",
    "            dp[i][2] = max(dp[i-1][2], dp[i-1][1]-prices[i])\n",
    "            dp[i][3] = max(dp[i-1][3], dp[i-1][2]+prices[i])\n",
    "        return max(dp[-1][1], dp[-1][3])\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.maxProfit([3, 3, 5, 0, 0, 3, 1, 4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c357312",
   "metadata": {},
   "source": [
    "[124. 二叉树中的最大路径和 - 力扣（LeetCode）](https://leetcode.cn/problems/binary-tree-maximum-path-sum/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "02ee2690",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 求二叉树的最大路径和\n",
    "# 遍历各个节点，找到以当前节点为根节点的所有路径中和最大的一个\n",
    "# 某个节点作为根节点对应的最大路径和=节点值+左节点最大贡献值+右节点最大贡献值\n",
    "\n",
    "# 使用深度优先搜索遍历所有节点\n",
    "\n",
    "# 节点对应最大贡献值：以该节点为起点的所有向下子路径中路径上最大的节点和，\n",
    "# 启动为对应节点，终点不一定为根节点\n",
    "# 根节点的最大贡献值等于其自身的值\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def maxPathSum(self, root: Optional[TreeNode]) -> int:\n",
    "        maxSum = -float('inf')\n",
    "\n",
    "        def maxGain(root: TreeNode) -> int:\n",
    "            nonlocal maxSum\n",
    "            # stop\n",
    "            if not root:\n",
    "                return 0\n",
    "\n",
    "            leftMaxGain = max(maxGain(root.left), 0)  # 如果子节点的最大贡献值小于0，就直接忽略\n",
    "            # 最大路径和直接以该节点开始\n",
    "            rightMaxGain = max(maxGain(root.right), 0)\n",
    "            # 计算root作为根节点时对应的最大路径和\n",
    "            maxSum = max(maxSum, leftMaxGain+rightMaxGain+root.val)\n",
    "            # 返回root对应的最大贡献值  # 左右子节点的最大值与当前节点值之和\n",
    "            return max(root.val+leftMaxGain, root.val+rightMaxGain)\n",
    "\n",
    "        maxGain(root)\n",
    "        return maxSum"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e611afd",
   "metadata": {},
   "source": [
    "[125. 验证回文串 - 力扣（LeetCode）](https://leetcode.cn/problems/valid-palindrome/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e2622559",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 字符串的三个方法s.isdigit() 是否为纯数字， s.isalpha() 是否为纯字母， s.lower():转化为最小\n",
    "# 先数据清洗\n",
    "# 双指针\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, s: str) -> bool:\n",
    "        Lst = []\n",
    "        for char in s:\n",
    "            if char.isalpha():\n",
    "                Lst.append(char.lower())\n",
    "            if char.isdigit():\n",
    "                Lst.append(char)\n",
    "\n",
    "        left, right = 0, len(Lst)-1\n",
    "        while left <= right:\n",
    "            if Lst[left] != Lst[right]:\n",
    "                return False\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return True\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.isPalindrome(\"A man, a plan, a canal: Panama\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c50b468",
   "metadata": {},
   "source": [
    "[126. 单词接龙 II - 力扣（LeetCode）](https://leetcode.cn/problems/word-ladder-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5b7aed2e",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "b60884ac",
   "metadata": {},
   "source": [
    "[127. 单词接龙 - 力扣（LeetCode）](https://leetcode.cn/problems/word-ladder/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "fc2d5687",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "## BFS\n",
    "\n",
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "\n",
    "## 找最短序列的长度\n",
    "## 使用虚拟结点：与当前的结点只相差一个字母的字符串作为相邻节点\n",
    "\n",
    "## 对所有单词进行hashmap\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:\n",
    "\n",
    "        import collections\n",
    "        edges = collections.defaultdict(list)\n",
    "        wordID = dict()\n",
    "\n",
    "        ## hashmap word\n",
    "        def hashmapWord(word:str)->None:\n",
    "            if word not in wordID:\n",
    "                wordID[word] = len(wordID)\n",
    "\n",
    "        ## 把当前单词作为新结点，并且找到其所有虚拟相邻结点，并将它们连接\n",
    "        ## 不同的结点的如果相邻，则它们肯定具有相同的虚拟相邻结点，并且会通过这个虚拟结点相连\n",
    "        def addEdge(word:str)->None:\n",
    "            nonlocal edges\n",
    "            hashmapWord(word)\n",
    "            recur_ID = wordID[word]\n",
    "            chars = list(word)\n",
    "            for i in range(len(chars)):\n",
    "                tmp = chars[i]\n",
    "                chars[i] = '*'\n",
    "                neighbor = ''.join(chars)\n",
    "                hashmapWord(neighbor)\n",
    "                neighbor_ID = wordID[neighbor]\n",
    "                edges[recur_ID].append(neighbor_ID)\n",
    "                edges[neighbor_ID].append(recur_ID)\n",
    "                chars[i] = tmp\n",
    "                \n",
    "        for word in wordList:\n",
    "            addEdge(word)\n",
    "        if endWord not in wordID: # endword 不在wordList中，不能到达\n",
    "            return 0\n",
    "        \n",
    "        addEdge(beginWord)\n",
    "\n",
    "        ## 使用bfs找到endword 与 beginword 之间的距离\n",
    "        dis = [-1]*len(wordID)\n",
    "        beginID, endID = wordID[beginWord], wordID[endWord]\n",
    "        dis[beginID] = 0 # beginID 与开始结点的距离\n",
    "        import queue\n",
    "        que = queue.Queue()\n",
    "        que.put(beginID)\n",
    "\n",
    "        while not que.empty():\n",
    "            recu_ID = que.get()\n",
    "            for neighbor in edges[recu_ID]:\n",
    "                if neighbor==endID:\n",
    "                    # print(dis)\n",
    "                    return (dis[recu_ID]+1)//2+1 # 返回的是路径结点的数目\n",
    "                if dis[neighbor]==-1: # 没有访问过\n",
    "                    dis[neighbor] = dis[recu_ID]+1\n",
    "                    que.put(neighbor)\n",
    "        # print(dis)\n",
    "        return 0\n",
    "\n",
    "\n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    beginWord = \"hit\"\n",
    "    endWord = \"cog\"\n",
    "    wordList = [\"hot\",\"dot\",\"dog\",\"lot\",\"log\",\"cog\"]\n",
    "    print(solv.ladderLength(beginWord,endWord,wordList))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "bb968f91",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "## 双向BFS\n",
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 使用双向BFS\n",
    "\n",
    "# 虚拟节点： 单词对于的相邻的虚拟节点，为所有与其单词相差为1的节点， 'hit'的虚拟相邻节点：'*it', 'h*t', 'hi*'\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:\n",
    "        import collections\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "\n",
    "        wordID = dict()\n",
    "        edges = collections.defaultdict(list)\n",
    "\n",
    "        # hashmap\n",
    "        def hashmapWord(word: str) -> None:\n",
    "            nonlocal wordID\n",
    "            if word not in wordID:\n",
    "                wordID[word] = len(wordID)\n",
    "\n",
    "        # 把一个结点和其邻接的虚拟结点相连\n",
    "        def addEdge(word: str) -> None:\n",
    "            nonlocal edges\n",
    "            hashmapWord(word)\n",
    "            recur_ID = wordID[word]\n",
    "            chars = list(word)\n",
    "            for i in range(len(chars)):\n",
    "                tmp = chars[i]\n",
    "                chars[i] = '*'\n",
    "                neighbor = ''.join(chars)\n",
    "                hashmapWord(neighbor)\n",
    "                neighbor_ID = wordID[neighbor]\n",
    "                edges[recur_ID].append(neighbor_ID)\n",
    "                edges[neighbor_ID].append(recur_ID)\n",
    "                chars[i] = tmp\n",
    "\n",
    "        # 构建图\n",
    "        for word in wordList:\n",
    "            addEdge(word)\n",
    "        addEdge(beginWord)\n",
    "\n",
    "        # 双向bfs搜索\n",
    "        import queue\n",
    "        # 前向搜索\n",
    "        preDist = [-1]*len(wordID)\n",
    "        beginID = wordID[beginWord]\n",
    "        preDist[beginID] = 0\n",
    "        preQue = queue.Queue()\n",
    "        preQue.put(beginID)\n",
    "\n",
    "        # 后向搜索\n",
    "        sufDist = [-1]*len(wordID)\n",
    "        endID = wordID[endWord]\n",
    "        sufDist[endID] = 0\n",
    "        sufQue = queue.Queue()\n",
    "        sufQue.put(endID)\n",
    "\n",
    "        while (not preQue.empty()) and (not sufQue.empty()):\n",
    "            preNode = preQue.get()\n",
    "            for preNeighbor in edges[preNode]:\n",
    "                if sufDist[preNeighbor] != -1:  # 相邻节点已经被后向搜索找到了\n",
    "                    # print(preDist)\n",
    "                    # print(sufDist)\n",
    "                    return (preDist[preNode]+1+sufDist[preNeighbor])//2+1\n",
    "                if preDist[preNeighbor] == -1:\n",
    "                    preDist[preNeighbor] = preDist[preNode]+1\n",
    "                    preQue.put(preNeighbor)\n",
    "\n",
    "            sufNode = sufQue.get()\n",
    "            for sufNeighbor in edges[sufNode]:\n",
    "                if preDist[sufNeighbor] != -1:  # 相邻节点已经被前向搜索找到了\n",
    "                    # print(preDist)\n",
    "                    # print(sufDist)\n",
    "                    return (sufDist[sufNode]+1+preDist[sufNeighbor])//2+1\n",
    "                if sufDist[sufNeighbor] == -1:\n",
    "                    sufDist[sufNeighbor] = sufDist[sufNode]+1\n",
    "                    sufQue.put(sufNeighbor)\n",
    "\n",
    "        return 0  # 没找到目标节点\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    solv = Solution()\n",
    "    beginWord = \"hit\"\n",
    "    endWord = \"cog\"\n",
    "    wordList = [\"hot\",\"dot\",\"tog\",\"cog\"]\n",
    "    print(solv.ladderLength(beginWord, endWord, wordList))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b45a9e94",
   "metadata": {},
   "source": [
    "[128. 最长连续序列 - 力扣（LeetCode）](https://leetcode.cn/problems/longest-consecutive-sequence/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e6ee9828",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "\n",
    "# 要求O(n)的计算复杂度，不能使用传统排序方法\n",
    "# 使用hashmap，统计\n",
    "# 找到第一个开始连续的数字num， num-1 不在列表中，开始统计最长的链\n",
    "# 跳过不是第一个连续的数字\n",
    "class Solution:\n",
    "    def longestConsecutive(self, nums: List[int]) -> int:\n",
    "        Dict = {num: 1 for num in nums}\n",
    "        longest = 0\n",
    "        for num in nums:\n",
    "            if num-1 not in Dict:\n",
    "                tmp = num+1\n",
    "                recur_longest = 1\n",
    "                while tmp in Dict:\n",
    "                    recur_longest += 1\n",
    "                    tmp += 1\n",
    "                longest = max(longest, recur_longest)\n",
    "        return longest\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78824ecc",
   "metadata": {},
   "source": [
    "[129. 求根节点到叶节点数字之和 - 力扣（LeetCode）](https://leetcode.cn/problems/sum-root-to-leaf-numbers/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "2bb4726f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumNumbers(self, root: Optional[TreeNode]) -> int:\n",
    "        # 回溯的方法找到每个叶子结点的路径\n",
    "        from copy import deepcopy\n",
    "        paths = []\n",
    "        # dfs\n",
    "\n",
    "        def dfs(root: TreeNode, total: int) -> None:\n",
    "            nonlocal paths\n",
    "            if not root.left and not root.right:  # 遇见叶子结点停止\n",
    "                total = total*10 + root.val\n",
    "                paths.append(total)\n",
    "                return\n",
    "\n",
    "            total = total*10+root.val\n",
    "            if root.left:\n",
    "                dfs(root.left, total)\n",
    "            if root.right:\n",
    "                dfs(root.right, total)\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return sum(paths)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    # build BinaryTree\n",
    "    def creatBT(pos: int, Lst: List[int]) -> TreeNode:\n",
    "        if pos >= len(Lst):\n",
    "            return None\n",
    "\n",
    "        root = TreeNode(Lst[pos])\n",
    "        root.left = creatBT(2*pos, Lst)\n",
    "        root.right = creatBT(2*pos+1, Lst)\n",
    "        return root\n",
    "    Lst = [0, 0, 1]\n",
    "    root = creatBT(1, Lst)\n",
    "    solv = Solution()\n",
    "    print(solv.sumNumbers(root))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "348054fe",
   "metadata": {},
   "source": [
    "[130. 被围绕的区域 - 力扣（LeetCode）](https://leetcode.cn/problems/surrounded-regions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "671f2de6",
   "metadata": {},
   "outputs": [],
   "source": [
    "## 基于深度优先搜索，dfs\n",
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        ## 先找到所有边缘的‘O’\n",
    "        # 以这些边缘‘O’为起点，找到所有相连的‘O’，并且将这些合格的‘O’标记为‘A’\n",
    "        ## 遍历矩阵，把‘A’变为‘O’，把‘O’变为X\n",
    "\n",
    "        n,m = len(board),len(board[0])\n",
    "        # 深度优先遍历 dfs\n",
    "        def dfs(x,y):\n",
    "            nonlocal board,n,m\n",
    "            if (0<=x<n) and (0<=y<m) and board[x][y]=='O':\n",
    "                board[x][y] = 'A'\n",
    "                ## 继续遍历当前点的邻居\n",
    "                dfs(x-1,y)\n",
    "                dfs(x+1,y)\n",
    "                dfs(x,y-1)\n",
    "                dfs(x,y+1)\n",
    "        \n",
    "        ## 找到边缘点\n",
    "        for i in range(n):\n",
    "            if board[i][0]=='O':\n",
    "                dfs(i,0)\n",
    "            if board[i][m-1]=='O':\n",
    "                dfs(i,m-1)\n",
    "        for j in range(m):\n",
    "            if board[0][j] =='O':\n",
    "                dfs(0,j)\n",
    "            if board[n-1][j] =='O':\n",
    "                dfs(n-1,j)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if board[i][j]=='O':\n",
    "                    board[i][j] = 'X'\n",
    "                if board[i][j] == 'A':\n",
    "                    board[i][j] = 'O'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e1627bb3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 基于广度优先搜索， bfs\n",
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, board: List[List[str]]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify board in-place instead.\n",
    "        \"\"\"\n",
    "        # 先找到所有边缘的‘O’\n",
    "        # 以边缘‘O’为为起点，向内搜索直到周边没有‘O’\n",
    "        n, m = len(board), len(board[0])\n",
    "\n",
    "        import queue\n",
    "        \n",
    "        # bfs\n",
    "        def bfs(x: int, y: int) -> None:\n",
    "            nonlocal board, n, m\n",
    "            if (0 <= x < n) and (0 <= y < m) and board[x][y] == 'O':\n",
    "                board[x][y] = 'A'\n",
    "                que = queue.Queue()\n",
    "                que.put((x, y))\n",
    "                while not que.empty():\n",
    "                    x1, y1 = que.get()\n",
    "                    bfs(x1-1, y1)\n",
    "                    bfs(x1+1, y1)\n",
    "                    bfs(x1, y1-1)\n",
    "                    bfs(x1, y1+1)\n",
    "\n",
    "        # 遍历边缘‘O’\n",
    "        for i in range(n):\n",
    "            if board[i][0] == 'O':\n",
    "                bfs(i, 0)\n",
    "            if board[i][m-1] == 'O':\n",
    "                bfs(i, m-1)\n",
    "        for j in range(m):\n",
    "            if board[0][j] == 'O':\n",
    "                bfs(0, j)\n",
    "            if board[n-1][j] == 'O':\n",
    "                bfs(n-1, j)\n",
    "\n",
    "        # 遍历矩阵:‘O’->‘X’，‘A’->‘O’\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if board[i][j] == 'O':\n",
    "                    board[i][j] = 'X'\n",
    "                if board[i][j] == 'A':\n",
    "                    board[i][j] = 'O'\n",
    "\n",
    "        marginO = []\n",
    "        for i in range(n):\n",
    "            if board[i][0] == 'O':\n",
    "                marginO.append((i, 0))\n",
    "            if board[i][m-1] == 'O':\n",
    "                marginO.append((i, m-1))\n",
    "        for j in range(m):\n",
    "            if board[0][j] == 'O':\n",
    "                marginO.append((0, j))\n",
    "            if board[n-1][j] == 'O':\n",
    "                marginO.append((n-1, j))\n",
    "        import queue\n",
    "\n",
    "        totalO = []\n",
    "        # 以边缘点为起点，向内搜索找到所有合适的‘O’\n",
    "        for Oitem in marginO:\n",
    "            i, j = Oitem\n",
    "            que = queue.Queue()\n",
    "            que.put((i, j))\n",
    "            stateDict = dict()  # 记录已经处理的位置\n",
    "            while not que.empty():\n",
    "                x, y = que.get()\n",
    "                totalO.append((x, y))  # 记录合格‘O’\n",
    "                stateDict[(x, y)] = 1  # 记录已经处理的点\n",
    "                neighbors = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]\n",
    "                for x1, y1 in neighbors:\n",
    "                    if (x1, y1) in stateDict:  # 跳过已经处理的位置\n",
    "                        continue\n",
    "                    if (0 <= x1 <= n-1) and (0 <= y1 <= m-1) and board[x1][y1] == 'O':\n",
    "                        que.put((x1, y1))  # 把当前‘O’加入队列\n",
    "\n",
    "        # hashmap\n",
    "        hashMap = {key: 1 for key in totalO}\n",
    "\n",
    "        # 遍历替换不合格的‘O’\n",
    "        for i in range(1, n-1):\n",
    "            for j in range(1, m-1):\n",
    "                # 如果相邻没有合格的‘O’，替换\n",
    "                if board[i][j] == 'O':\n",
    "                    neighbors = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]\n",
    "                    board[i][j] = 'X'\n",
    "                    for (x1, y1) in neighbors:\n",
    "                        if (x1, y1) in hashMap:\n",
    "                            board[i][j] = 'O'\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af534910",
   "metadata": {},
   "source": [
    "[131. 分割回文串 - 力扣（LeetCode）](https://leetcode.cn/problems/palindrome-partitioning/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c22e71e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from turtle import back\n",
    "from typing import List, Optional\n",
    "\n",
    "# 使用回溯方法枚举每一种可能\n",
    "# 递归的找出当前段的回文前缀，直到后缀为空\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, s: str) -> List[List[str]]:\n",
    "\n",
    "        res = []\n",
    "        n = len(s)\n",
    "        # 判定是否为回文\n",
    "\n",
    "        def checkHuiWen(Lst: List[int]) -> bool:\n",
    "            left, right = 0, len(Lst)-1\n",
    "            while left <= right:\n",
    "                if Lst[left] != Lst[right]:\n",
    "                    return False\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            return True\n",
    "\n",
    "        # 回溯\n",
    "        def backTrack(pos: int, path: List[int]) -> None:\n",
    "            if pos == n:\n",
    "                nonlocal res\n",
    "                res.append(path)\n",
    "\n",
    "            for i in range(pos, n):\n",
    "                prePart = s[pos:i+1]\n",
    "                if checkHuiWen(prePart):\n",
    "                    backTrack(i+1, path+[prePart])\n",
    "\n",
    "        backTrack(0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a8e86d6",
   "metadata": {},
   "source": [
    "[132. 分割回文串 II - 力扣（LeetCode）](https://leetcode.cn/problems/palindrome-partitioning-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "631f85bd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "\n",
    "# 最小的分割次数\n",
    "# 两次动态规划\n",
    "# 1)使用动态规划判定每个子段是否为回文\n",
    "# state[i][j]: 表示s[i:j+1] 是否为回文字串\n",
    "# 转移方程\n",
    "# state[i][j] = True  ,if i>=j\n",
    "#             = (s[i]==s[j]) and state[i+1][j-1], otherwis\n",
    "# 2) 使用动态规划判定当前段最小分割数\n",
    "# dp[i]: 表示s[i:]对应的最小分割数\n",
    "# dp[i] = min(0, 1+dp[i+1], 1+dp[i+2], 1+dp[n-1]), 每一项的前缀为回文时，才能参与\n",
    "# return dp[0]\n",
    "\n",
    "class Solution:\n",
    "    def minCut(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # 使用动态规划判断各个子段是否为回文\n",
    "        # 定义 state[i][j]: 对应s[i:j+1] 是否为回文字串\n",
    "        # state[i][j] = True, when i==j\n",
    "        # state[i][j] = (s[i]==s[j]) and state[i+1][j-1]\n",
    "        state = [[True]*n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                state[i][j] = (s[i] == s[j]) and state[i+1][j-1]\n",
    "\n",
    "        if state[0][n-1]:\n",
    "            return 0\n",
    "\n",
    "        # 使用动态规划统计s[i:]对应的最小切割次数\n",
    "        # 定义dp[i] 表示s[i:]对应的最新回文切割次数\n",
    "        # dp[i] = min(0,1+dp[i+1],1+dp[i+2],...,1+dp[n]), 对应的项只有在前缀为回文字符串的时候才参与计算\n",
    "        # dp[n] = 0\n",
    "        dp = [float('inf')]*n\n",
    "        dp[n-1] = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if state[i][n-1]:\n",
    "                dp[i] = 0\n",
    "                continue\n",
    "            for j in range(i, n):\n",
    "                if state[i][j]:\n",
    "                    tmp = 1+dp[j+1]\n",
    "                    dp[i] = min(dp[i], tmp)\n",
    "        return dp[0]\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    s = \"ab\"\n",
    "    solv = Solution()\n",
    "    print(solv.minCut(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11383f5a",
   "metadata": {},
   "source": [
    "[133. 克隆图 - 力扣（LeetCode）](https://leetcode.cn/problems/clone-graph/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f6158668",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 克隆图\n",
    "\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=0, neighbors=None):\n",
    "        self.val = val\n",
    "        self.neighbors = neighbors if neighbors is not None else []\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        # bfs\n",
    "        import queue\n",
    "        Dict = dict()\n",
    "        if not node:\n",
    "            return None\n",
    "\n",
    "        que = queue.Queue()\n",
    "        que.put(node)\n",
    "        while not que.empty():\n",
    "            recur = que.get()\n",
    "            Dict[recur.val] = [neighbor.val for neighbor in recur.neighbors]\n",
    "            for neighbor in recur.neighbors:\n",
    "                if neighbor.val not in Dict:\n",
    "                    que.put(neighbor)\n",
    "        keys = sorted(Dict.keys())\n",
    "        res = []\n",
    "        for key in keys:\n",
    "            res.append(Dict[key])\n",
    "\n",
    "        newNodes = [Node(val=i) for i in range(1, len(res)+1)]\n",
    "\n",
    "        for i in range(len(res)):\n",
    "            nids = res[i]\n",
    "            neighbors = [newNodes[id-1] for id in nids]\n",
    "            newNodes[i].neighbors = neighbors\n",
    "        return newNodes[0]\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    Lst = [[2, 4], [1, 3], [2, 4], [1, 3]]\n",
    "    n = len(Lst)\n",
    "    nodes = [Node(val=i) for i in range(1, n+1)]\n",
    "    for i in range(n):\n",
    "        nIDs = Lst[i]\n",
    "        neighbors = [nodes[id-1] for id in nIDs]\n",
    "        nodes[i].neighbors = neighbors\n",
    "    node = nodes[0]\n",
    "    solv = Solution()\n",
    "    print(solv.cloneGraph(node))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2188d9f8",
   "metadata": {},
   "source": [
    "[134. 加油站 - 力扣（LeetCode）](https://leetcode.cn/problems/gas-station/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7e753312",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 逐个遍历时间超时\n",
    "# 跳过无需判断的起点\n",
    "# 计算：规律，从x->y,y表示从x开始第一个无法到达的点,则x->y中间任意一个点z都无法到达y\n",
    "# \\sum_{i=x->y} gas[i]  <  \\sum_{i=x->y} cost[i]  # x无法到达y\n",
    "# \\sum_{i=x->z} gas[i]  >  \\sum_{i=x->y} cost[i]  # x可以到达z\n",
    "# \\sum_{i=z->y} gas[i] = \\sum_{i=x->y}gas[i]-\\sum_{i=x->z-1}gas[i]\n",
    "#                      < \\sum_{i=x->y}cost[i] - \\sum_{i=x->z-1}gas[i]\n",
    "#                      < \\sum_{i=x->y}cost[i] - \\sum_{i=x->z-1}cost[i]\n",
    "#                      = \\sum_{i=z->y}cost[i]\n",
    "#\n",
    "# \\sum_{i=z->y} gas[i] < \\sum_{i=z->y}cost[i]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:\n",
    "        # 遍历\n",
    "        # 当cost[i]>gas[i]时不能作为起点\n",
    "        n = len(gas)\n",
    "\n",
    "        lst = []\n",
    "        rest = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if cost[i] > gas[i]:\n",
    "                i += 1\n",
    "                continue\n",
    "            rest = 0\n",
    "            for k in range(n+1):\n",
    "                rest += gas[(i+k) % n]-cost[(i+k) % n]\n",
    "                if rest < 0:\n",
    "                    break\n",
    "            if rest >= 0:\n",
    "                return i\n",
    "            else:\n",
    "                i = (i+k)\n",
    "        return -1\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    gas = [2, 3, 4]\n",
    "    cost = [3, 4, 3]\n",
    "    solv = Solution()\n",
    "    print(solv.canCompleteCircuit(gas, cost))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b360868",
   "metadata": {},
   "source": [
    "[135. 分发糖果 - 力扣（LeetCode）](https://leetcode.cn/problems/candy/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "092209fa",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 贪婪分糖果问题\n",
    "# 左侧遍历一遍，ratings[i]>ratings[i-1]时， nums[i]=nums[i]+1, 否则 nums[i]=1\n",
    "# 右侧遍历一遍，ratings[i]>ratings[i+1]时， nums[i]=max(nums[i],nums[i]+1), 否则不做改变\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        n = len(ratings)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "\n",
    "        nums = [0]*n\n",
    "        # 左侧遍历\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                if ratings[i] <= ratings[i+1]:\n",
    "                    nums[i] = 1\n",
    "                continue\n",
    "            if ratings[i] > ratings[i-1]:\n",
    "                nums[i] = nums[i-1]+1\n",
    "            else:\n",
    "                nums[i] = 1\n",
    "        # 合并求和过程，到右侧遍历中\n",
    "        reSum = nums[n-1]\n",
    "        # 右侧遍历\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if ratings[i] > ratings[i+1]:\n",
    "                nums[i] = max(nums[i], nums[i+1]+1)\n",
    "            reSum += nums[i]\n",
    "\n",
    "        return reSum\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.candy([1, 0, 2]))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e28191f",
   "metadata": {},
   "source": [
    "[136. 只出现一次的数字 - 力扣（LeetCode）](https://leetcode.cn/problems/single-number/submissions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "b1e28176",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 异或操作， a^a=0; 0^a=a; a^b^c=a^c^b\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        re = 0\n",
    "        for num in nums:\n",
    "            re = re ^ num\n",
    "        return re\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.singleNumber([5, 2, 1, 2, 1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b952755d",
   "metadata": {},
   "source": [
    "[137. 只出现一次的数字 II - 力扣（LeetCode）](https://leetcode.cn/problems/single-number-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "0e6e8c45",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "class Solution:\n",
    "    def singleNumber(self, nums: List[int]) -> int:\n",
    "        ## 把数据转成32位二进制，统计每一位上1的数目，1的数目只有三个可能：1个，0个，3个，所有对3取余就是目标\n",
    "        re = 0\n",
    "        for i in range(32):\n",
    "            mask = 1<<i\n",
    "            cnt = 0\n",
    "            for num in nums:\n",
    "                if (num&mask)!=0:\n",
    "                    cnt+=1\n",
    "            if cnt%3!=0:\n",
    "                re = re | mask\n",
    "        # 因为负数的符号位被进行了 ‘或’ 操作，所以符号位丢失\n",
    "        # 因此要手动，判断符号位，如果为1，转化为对应的复数2**32-re\n",
    "        if cnt%3!=0:  # 最高位为1\n",
    "            re = (~re + 1)&0xffffffff\n",
    "            re = -re\n",
    "        return re\n",
    "\n",
    "\n",
    "if __name__=='__main__':\n",
    "    solv = Solution()\n",
    "    print(solv.singleNumber([5,-2,1,-2,1,-2,1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dff76542",
   "metadata": {},
   "source": [
    "[138. 复制带随机指针的链表 - 力扣（LeetCode）](https://leetcode.cn/problems/copy-list-with-random-pointer/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "375c61ea",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "## 遍历两次链表\n",
    "# 第一次：读取所有结点的值到列表valLst，并且把序号赋值给结点\n",
    "# 第二次：读取random指向结点的序号值到列表randLst\n",
    "## 根据数值列表valLst，构建新链表\n",
    "# 根据randLst构建新链表结点random的指向\n",
    "\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not head:\n",
    "            return None\n",
    "\n",
    "        valLst = []\n",
    "        randLst = []\n",
    "        # 读取链表的值，并且对所有结点编号\n",
    "        pos = head\n",
    "        i = 0\n",
    "        while pos:\n",
    "            valLst.append(pos.val)\n",
    "            pos.val = i\n",
    "            pos = pos.next\n",
    "            i+=1\n",
    "        \n",
    "        # 读取random指向\n",
    "        pos = head\n",
    "        while pos:\n",
    "            if not pos.random:\n",
    "                randLst.append(-1) # 收集新的结点的序号\n",
    "            else:\n",
    "                randLst.append(pos.random.val)\n",
    "            pos = pos.next\n",
    "\n",
    "        ## 新建链表\n",
    "        n = len(valLst)\n",
    "        newNodes = [Node(val) for val in valLst] # 新建链表\n",
    "        # 重建结点的指针指向\n",
    "        for i in range(n-1):\n",
    "            newNodes[i].next = newNodes[i+1]\n",
    "            if randLst[i]==-1:\n",
    "                newNodes[i].random = None\n",
    "            else:\n",
    "                newNodes[i].random = newNodes[randLst[i]]\n",
    "        if randLst[n-1]==-1:\n",
    "            newNodes[n-1].random = None\n",
    "        else:\n",
    "            newNodes[n-1].random = newNodes[randLst[n-1]]\n",
    "        return newNodes[0]\n",
    "\n",
    "if __name__=='__main__':\n",
    "    Lst = [[7,None],[13,0],[11,4],[10,2],[1,0]]\n",
    "    num = len(Lst)\n",
    "    newNodes = []\n",
    "    for node in Lst:\n",
    "        newNodes.append(Node(node[0]))\n",
    "\n",
    "    for i in range(len(Lst)-1):\n",
    "        newNodes[i].next = newNodes[i+1]\n",
    "        if Lst[i][1]==None:\n",
    "            newNodes[i].random = None\n",
    "        else:\n",
    "            newNodes[i].random = newNodes[Lst[i][1]]\n",
    "    if Lst[num-1][1]!=None:\n",
    "        newNodes[num-1].random = newNodes[Lst[num-1][1]]\n",
    "    head = newNodes[0]\n",
    "    solv = Solution()\n",
    "    solv.copyRandomList(head)       "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9454411a",
   "metadata": {},
   "source": [
    "[139. 单词拆分 - 力扣（LeetCode）](https://leetcode.cn/problems/word-break/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "05a18af9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "# coding=utf-8\n",
    "from typing import List,Optional\n",
    "\n",
    "## 字典hash化，把字符串分为两个部分，前导单词+子字符串\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "        n = len(s)\n",
    "        hashMap = set(wordDict)\n",
    "        \n",
    "        # 单回溯超时\n",
    "        ## 动态规划\n",
    "        # 定义： dp[i]: s[i:] 是否可以由字典组成\n",
    "        # 转移方程\n",
    "        # dp[i] = ((s[i:i+1] in hashMap) & dp[i+1])\n",
    "        #         or ((s[i:i+2] in hashMap) & dp[i+2])\n",
    "        #         ...\n",
    "        #         or ((s[i:n]) in hashMap) & dp[n]\n",
    "        # dp[n] = True\n",
    "\n",
    "        dp = [False]*(n+1)\n",
    "        dp[n] = True\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n+1):\n",
    "                part = s[i:j]\n",
    "                dp[i] = dp[i] or ((part in hashMap) & dp[j])\n",
    "        return dp[0]\n",
    "      \n",
    "\n",
    "\n",
    "if __name__=='__main__':\n",
    "    s = \"aaaaaaa\"\n",
    "    wordDict = [\"aaa\",\"aaaa\"]\n",
    "    solv = Solution()\n",
    "    print(solv.wordBreak(s, wordDict))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f7d7ef0",
   "metadata": {},
   "source": [
    "[140. 单词拆分 II - 力扣（LeetCode）](https://leetcode.cn/problems/word-break-ii/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a724aa33",
   "metadata": {},
   "outputs": [],
   "source": [
    "# coding=utf-8\n",
    "from typing import List, Optional\n",
    "\n",
    "# 要返回所有可能的序列，因此使用回溯遍历\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:\n",
    "        from copy import deepcopy\n",
    "        n = len(s)\n",
    "        hashMap = set(wordDict)\n",
    "        res = []\n",
    "\n",
    "        # 回溯\n",
    "        def backTrack(pos: int, Lst: List[int]) -> None:\n",
    "            nonlocal n, s, hashMap\n",
    "            if pos >= n:\n",
    "                res.append(deepcopy(Lst))\n",
    "                return\n",
    "\n",
    "            for i in range(pos+1, n+1):\n",
    "                part = s[pos:i]\n",
    "                if part in hashMap:\n",
    "                    backTrack(i, Lst+[part])\n",
    "\n",
    "        backTrack(0, [])\n",
    "        tmp = []\n",
    "        for words in res:\n",
    "            tmp.append(' '.join(words))\n",
    "\n",
    "        return tmp\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    s = \"catsanddog\"\n",
    "    wordDict = [\"cat\", \"cats\", \"and\", \"sand\", \"dog\"]\n",
    "    solv = Solution()\n",
    "    print(solv.wordBreak(s, wordDict))\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
